package com.chenken;


/**
 * 插入排序-优化2
 * 将比较转为使用二分查找法定位最终位置
 */
public class InsertionSort3<T extends Comparable<T>> extends Sort<T>{

	@Override
	protected void sort() {
		//	从下标1开始，每一个元素都要往左比较
		for(int begin = 1;begin<arrays.length;begin++) {
			T v = arrays[begin];
			int insertIndex = binarySearch(arrays,v);//计算出元素v应该插入的位置
			for(int i = begin;i>insertIndex;i--) {
				arrays[i] = arrays[i-1];//	将元素往后挪动一位
			}
			arrays[insertIndex] = v;//将元素v插入到计算好的位置
		}
	}
	
	/**
	 * 查找v在有序数组array中的待插入位置
	 * @param array
	 * @param v
	 * @return
	 */
	public int binarySearch(T[] array,T v){
		int begin = 0;
		int end = array.length;
		while(begin < end) {
			int middle = (begin + end) >> 1;
			if(compare(v, array[middle])<0){
				end = middle;
			}else {
				begin = middle+1;
			}
		}
		return begin;
	}

	/**
	 * 查找v在有序数组array中的位置
	 * @param array
	 * @param v
	 * @return
	 */
	public int binaryIndex(T[] array,T v){
		int begin = 0;
		int end = array.length;
		while(begin < end) {
			int middle = (begin + end) >> 1;
			if(compare(v, array[middle])<0){
				end = middle;
			}else if(compare(v, array[middle])>0){
				begin = middle+1;
			}else {
				return middle;
			}
		}
		return -1;
	}
}
